package 牛客.树;
/*
 *@Author   helen
 *@Date     2021/4/9 10:28
 *@Descriptions
        给定一个二叉树，返回该二叉树层序遍历的结果，（从左到右，一层一层地遍历）
 */
import org.junit.Test;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

public class 按层序遍历二叉树 {
    public ArrayList<ArrayList<Integer>> levelOrder (BTreeNode<Integer> root) {
        // write code here
        ArrayList<ArrayList<Integer>> list2 = new ArrayList<>();
        Queue<BTreeNode> queue = new LinkedList<>();
        if(root == null)
            return list2;
       queue.add(root);

       while(!queue.isEmpty()){
           ArrayList<Integer> list = new ArrayList<>();
           int size = queue.size();          //当前层的元素个数

           for (int i = 0; i < size; i++) {
               BTreeNode<Integer> poll = queue.poll();
               list.add(poll.data);     //访问队头结点
               if(poll.left != null)
                   queue.add(poll.left);  //把左结点入队
               if(poll.right != null)
                   queue.add(poll.right);  //把右结点入队
           }
           list2.add(list);
       }
        return list2;
    }

    @Test
    public void test(){
        BTree<Integer> btree = new BTree<>();
        for (int i = 0; i < 10; i++) {
            btree.RandomCreatTree(btree.root, i);
        }
        System.out.println("=============按层序遍历数===============");
        按层序遍历二叉树 object = new 按层序遍历二叉树();
        ArrayList<ArrayList<Integer>> list = object.levelOrder(btree.root);
        System.out.println(list.toString());
    }
}
